import "babel-polyfill";
import {islice} from "../../algorithm/array";
import {enumerate, map} from "../../algorithm/iterator";
import Integer, {range} from "../number/integer";
import {gcd} from "./gcd";
import {small_primes, initPrimes, isPrime} from "./prime";
import {sqrt, sqrtIfPerfect} from "./nth-root";

const {zero, one, eq, compare, negate, add, subtract, multiply, square, divmod, divide, mod, exactDivide, shl} = Integer;

var trial = function(n) {
    for (let p of small_primes) {
        if (mod(n, p).sign === 0) {
            return p;
        }
    }
};

var pollardRho = function(n, limit = Infinity) {
    var initial = function*() {
        var [x0, a] = [zero, zero];
        while (true) {
            if (eq(x0, a)) {
                x0 = add(x0, one);
                a = one;
            } else {
                a = add(a, one);
            }
            yield [x0, a];
        }
    };

    for (let [x0, a] of initial()) {
        let f = x => mod(add(square(x), a), n);
        let x = f(x0);
        let y = f(x);
        if (eq(x, y)) {
            continue;
        }
        let g = gcd(subtract(x, y), n);
        if (!eq(g, one)) {
            return g;
        }
        let overflow = true;
        for (let k = 1; k < limit; k *= 2) {
            let fail = false;
            x = y;
            for (let i = 0; i < k; ++i) {
                y = f(y);
            }
            for (let i = 0; i < k; ++i) {
                y = f(y);
                if (eq(x, y)) {
                    fail = true;
                    break;
                }
                let g = gcd(subtract(x, y), n);
                if (!eq(g, one)) {
                    return g;
                }
            }
            if (fail) {
                overflow = false;
                break;
            }
        }
        if (overflow) {
            return;
        }
    }
};

var squfofSimple = function(n) {
    var root = sqrtIfPerfect(n);
    if (root !== undefined) {
        return root;
    }
    for (let N of range(n, undefined, n)) {
        let m = sqrt(N);
        let m1 = zero;
        let [p0, p1, q0, q1] = [zero, m, one, subtract(N, square(m))];
        while (true) {
            [p0, p1] = [p1, p0];
            [q0, q1] = [q1, q0];
            let [b, r] = divmod(add(m, p0), q0);
            p1 = subtract(m, r);
            q1 = add(q1, multiply(b, subtract(p0, p1)));
            m1 = sqrtIfPerfect(q1);
            if (m1 !== undefined) {
                break;
            }
        }
        q0 = m1;
        p1 = subtract(m, mod(subtract(m, p1), q0));
        q1 = exactDivide(subtract(N, square(p1)), q0);
        while (true) {
            [p0, p1] = [p1, p0];
            [q0, q1] = [q1, q0];
            [b, r] = divmod(add(m, p0), q0);
            p1 = subtract(m, r);
            if (eq(p0, p1)) {
                break;
            }
            q1 = add(q1, multiply(b, subtract(p0, p1)));
        }
        let g = gcd(n, p0);
        if (!eq(g, one) && !eq(g, n)) {
            return g;
        }
    }
};

var squfof = function(n, m = 1) {
    var root = sqrtIfPerfect(n);
    if (root !== undefined) {
        return root;
    }

    var d = multiply(m, n);
    if ((d.lastLimb & 3) === 1) {
        d = shl(d, 1);
    }
    m = shl(m, 1);
    var s = sqrt(d);
    var q_hat = one;
    var p = s;
    var q = subtract(d, square(p));
    var l = shl(sqrt(shl(sqrt(d), 1)), 1);
    var b = shl(l, 1);
    var queue = [];

    for (let i of range()) {
        if (compare(i, b) > 0) {
            return;
        }
        let [little_q, r0] = divmod(add(s, p), q);
        let p_prime = subtract(s, r0);
        let g = exactDivide(q, gcd(q, m));
        if (compare(g, l) <= 0) {
            queue.push([g, mod(p, g)]);
        }
        [q, q_hat] = [add(q_hat, multiply(little_q, subtract(p, p_prime))), q];
        p = p_prime;
        if ((i.lastLimb & 1) === 0) {
            let r = sqrtIfPerfect(q);
            if (r !== undefined) {
                let z;
                for (z = 0; z < queue.length; ++z) {
                    let [x, y] = queue[z];
                    if (eq(x, r) && mod(subtract(p, y), r).sign === 0) {
                        break;
                    }
                }
                if (z === queue.length) {
                    break;
                }
                if (eq(r, one)) {
                    return;
                }
                queue.splice(0, z + 1);
            }
        }
    }

    q_hat = sqrt(q);
    p = subtract(s, mod(subtract(s, p), q_hat));
    q = exactDivide(subtract(d, square(p)), q_hat);

    for (let i of range(one, b)) {
        let [little_q, r0] = divmod(add(s, p), q);
        let p_prime = subtract(s, r0);
        if (eq(p, p_prime)) {
            break;
        }
        [q, q_hat] = [add(q_hat, multiply(little_q, subtract(p, p_prime))), q];
        p = p_prime;
    }
    return exactDivide(q, gcd(q, m));
};

var factorBigNumbers = function(n) {
    var n1 = pollardRho(n, 0x1000);
    if (n1 !== undefined) {
        return n1;
    }
    for (let m of [1, 3, 5, 7, 11, 15, 21, 33, 35, 55, 77, 105, 165, 231, 385, 1155]) {
        let q = squfof(n, m);
        if (q !== undefined) {
            return q;
        }
    }
    return squfofSimple(n);
};

var merge = function*(iterator1, iterator2) {
    var next1 = iterator1.next();
    var next2 = iterator2.next();
    while (!next1.done && !next2.done) {
        let x = next1.value;
        let y = next2.value;
        let comparison = compare(x[0], y[0]);
        if (comparison < 0) {
            yield x;
            next1 = iterator1.next();
        } else if (comparison > 0) {
            yield y;
            next2 = iterator2.next();
        } else {
            yield [x[0], x[1] + y[1]];
            next1 = iterator1.next();
            next2 = iterator2.next();
        }
    }
    while (!next1.done) {
        yield next1.value;
        next1 = iterator1.next();
    }
    while (!next2.done) {
        yield next2.value;
        next2 = iterator2.next();
    }
};

export default function* factor(n) {
    n = Integer.from(n);
    if (n.sign === 0) {
        yield [zero, 1];
    } else if (n.sign < 0) {
        yield [Integer[-1], 1];
        yield* factor(negate(n));
    } else if (compare(n, one) === 0) {
    } else if (isPrime(n)) {
        yield [n, 1];
    } else {
        let p = trial(n);
        if (p !== undefined) {
            let k = 0;
            while (true) {
                let [b, r] = divmod(n, p);
                if (r.sign) {
                    break;
                } else {
                    ++k;
                    n = b;
                }
            }
            yield [p, k];
            yield* factor(n);
        } else {
            let m1 = factorBigNumbers(n);
            let m2 = exactDivide(n, m1);
            yield* merge(factor(m1), factor(m2));
        }
    }
};

export var prettyPrint = function() {
    var list = [...this::map(([p, k]) => k === 1 ? `${p}` : `${p}^${k}`)];
    return list.length === 0 ? "1" : list.join(" * ");
};
